﻿namespace Leetcode.N0332;
public class Solution
{
    public IList<string> FindItinerary(IList<IList<string>> tickets)
    {
        tickets = tickets.OrderBy(i => i[1]).ToList();
        var ticketsStart = this.BuildTickersStart(tickets);

        foreach (var item in ticketsStart["JFK"])
        {
            var visisted = new bool[tickets.Count];
            var visitedPath = new Stack<string>();
            visitedPath.Push("JFK");
            if (this.Dsp(item, ticketsStart, tickets, visisted, visitedPath, 0))
            {
                return visitedPath.Reverse().ToList();
            }
        }

        return new List<string>();
    }

    private bool Dsp(int fromTicketIndex,
    IDictionary<string, IList<int>> ticketsStart,
    IList<IList<string>> tickets,
     bool[] visited,
     Stack<string> visitedPath,
     int visitedCount)
    {
        var ticket = tickets[fromTicketIndex];
        visited[fromTicketIndex] = true;
        visitedPath.Push(ticket[1]);
        visitedCount++;
        if (visitedCount == tickets.Count)
        {
            return true;
        }

        if (ticketsStart.ContainsKey(ticket[1]))
        {
            var nextTickets = ticketsStart[ticket[1]];
            foreach (var nextTicket in nextTickets)
            {
                if (visited[nextTicket])
                {
                    continue;
                }

                if (this.Dsp(nextTicket, ticketsStart, tickets, visited, visitedPath, visitedCount))
                {
                    return true;
                }
            }

        }

        visitedPath.Pop();
        visited[fromTicketIndex] = false;

        return false;
    }

    private IDictionary<string, IList<int>> BuildTickersStart(IList<IList<string>> tickets)
    {
        var result = new Dictionary<string, IList<int>>();
        for (var i = 0; i < tickets.Count; i++)
        {
            var from = tickets[i][0];
            if (!result.ContainsKey(from))
            {
                result.Add(from, new List<int>());
            }
            result[from].Add(i);
        }
        return result;
    }
}